﻿/*
题目：柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        // 单调栈
        // 维护单调递增，遇到小的就可以结算
        // 因为左边的柱子可以一起参与结算，否则如果左边的柱子太高，会导致该柱子结算错误

        stack<int> stk;
        int len = heights.size();

        int res = 0;
        for (int i = 0; i <= len; i++) {
            // 出现了更矮的，那么当前柱子就无法参与后面的结算了
            while (!stk.empty() && (i == len || heights[stk.top()] > heights[i])) {
                int h = heights[stk.top()];
                stk.pop();

                int left = stk.empty() ? -1 : stk.top();
                int w = i - left - 1;

                res = max(res, h * w);
            }
            stk.push(i);
        }

        return res;
    }
};